class Solution
{
public:
    int maximalSquare(vector<vector<char>> &matrix)
    {
        return dynamicProgramming(matrix);
    }

private:
    int dynamicProgramming(vector<vector<char>> &matrix)
    {
        // O(mn)
        int height = matrix.size();
        int width = matrix[0].size();
        int maxFound = 0;
        vector<vector<int>> maxMap(height, vector<int>(width, 0));
        for (int i = 0; i < height; ++i)
        {
            for (int j = 0; j < width; ++j)
            {
                if (matrix[i][j] == '1')
                {
                    if (i == 0 || j == 0)
                    {
                        maxMap[i][j] = 1;
                    }
                    else
                    {
                        int maxToExtend = maxMap[i - 1][j - 1];
                        if (maxMap[i - 1][j] < maxToExtend)
                        {
                            maxToExtend = maxMap[i - 1][j];
                        }
                        if (maxMap[i][j - 1] < maxToExtend)
                        {
                            maxToExtend = maxMap[i][j - 1];
                        }
                        maxMap[i][j] = 1 + maxToExtend;
                    }
                }
                else
                {
                    maxMap[i][j] = 0;
                }
                if (maxMap[i][j] > maxFound)
                {
                    maxFound = maxMap[i][j];
                }
            }
        }
        return maxFound * maxFound;
    }

    int enumeration(vector<vector<char>> &matrix)
    {
        // O(mn*min(m,n)^2)
        int height = matrix.size();
        int width = matrix[0].size();
        int maxFound = 0;
        for (int i = 0; i < height - maxFound; ++i)
        {
            for (int j = 0; j < width - maxFound; ++j)
            {
                int toVerify = maxFound + 1;
                bool valid = true;
                while (i + toVerify <= height && j + toVerify <= width)
                {
                    for (int x = 0; x < toVerify; ++x)
                    {
                        for (int y = 0; y < toVerify; ++y)
                        {
                            if (matrix[i + x][j + y] != '1')
                            {
                                valid = false;
                            }
                        }
                    }
                    if (valid)
                    {
                        maxFound = toVerify;
                        ++toVerify;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        return maxFound * maxFound;
    }
};